Consigne: Montrer que si \(p\) est un nombre premier et si \(a\in{\Bbb Z}\), alors $$a^p\equiv a\pmod p$$ (petit théorème de Fermat)
Initialisation de la récurrence sur \(a\)
On procède par récurrence sur \(a\).
Initialisation : pour \(a=0\), alors on a évidemment $$0\equiv0\pmod p$$
Hérédité avec la formule du binôme de Newton
Hérédité : montrons que \(\left( a^p\equiv a\pmod p\right)\implies\left((a+1)^p\equiv a+1\pmod p\right)\)
Exprimons \((a+1)^p\) à l'aide de la formule du binôme de Newton : $$\begin{align}(a+1)^p&=\sum^p_{i=0}\binom{p}{i}a^i\\ &=a^p+\binom{p}{p-1}a^{p-1}+\binom{p}{p-2}a^{p-2}+\ldots+\binom p1+1\end{align}$$
Les coefficients binomiaux de \(p\) sont des multiples de \(p\)
Or, on a : $$\forall p\notin\{0,i\},\quad\binom pi=\frac{p!}{i!(p-i)!}\equiv0\pmod p$$
On a donc :$$\begin{align}(a+1)^p&\equiv a^p+1\pmod p\\ &\equiv a+1\pmod p\end{align}$$ (d'après l'hypothèse de récurrence)
(Raisonnement par récurrence, Formule du binôme de Newton, Coefficient binomial)